package history

func quickSortNike(nums []int) {
	quickSortDfs(nums, 0, len(nums)-1)
}

func quickSortDfs(nums []int, low, high int) {
	if low < high {
		var left = low
		var right = high
		var val = nums[left]
		for left < right {
			if left < right && nums[right] > val {
				right--
			}
			if left < right {
				nums[left] = nums[right]
				left++
			}
			if left < right && nums[left] < val {
				left++
			}
			if left < right {
				nums[right] = nums[left]
				right--
			}
		}
		nums[left] = val
		quickSortDfs(nums, low, left-1)
		quickSortDfs(nums, left+1, high)
	}
}
